#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>

using namespace std;

// 2616. 最小化数对的最大差值
// https://leetcode.cn/problems/minimize-the-maximum-difference-of-pairs/description/?envType=daily-question&envId=2025-06-13

class Solution1
{
public:
    int minimizeMax(vector<int> &nums, int p)
    {
        set<int> recordNumber;
        for (int n : nums)
        {
            auto ret = recordNumber.insert(n);
            if (!ret.second)
            {
                recordNumber.erase(ret.first);
                p--;
                if (p <= 0)
                {
                    return 0;
                }
            }
        }
        priority_queue<int, vector<int>, greater<int>> res;
        for (auto it = recordNumber.begin(); it != --recordNumber.end();)
        {
            auto it1 = it;
            auto it2 = ++it;
            res.push(*it2 - *it1);
        }
        while (p != 1)
        {
            p--;
            res.pop();
        }
        return res.top();
    }
};

class Solution {
public:
    bool isStandard(vector<int>&nums, int p, int sub){
        for (int i = 0; i + 1 < nums.size(); i++){
            if(nums[i + 1] - nums[i] <= sub){
                p--;
                i++;
            }
        }
        return p <= 0;
    }
    int minimizeMax(vector<int>& nums, int p) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int ans = nums[n - 1];
        int left = 0;
        int right = ans;
        while(left <= right){
            int mid = (right - left) / 2 + left;
            if(isStandard(nums, p, mid)){
                ans = mid;
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return ans;
    }
};

int main()
{
    vector<int> nums{10, 1, 2, 7, 1, 3};
    int p = 2;
    Solution solution{};
    cout << solution.minimizeMax(nums, p) << endl;
    return 0;
}